package com.learn.algorlthm;

/**
 * @classname:
 * @Description:反转链表
 * @author: yfpu(fengpu.yang @ ucarinc.com)
 * @Date: 2018-07-26 17:03
 */
public class Learn24 {

    //递归
    public static ListNode reverseList(ListNode head) {
        if (head == null || head.next == null)
            return head;

        ListNode next = head.next;

        ListNode newListNode = reverseList(next);

        head.next = null;
        next.next = head;

        return newListNode;
    }

    //迭代
    public static ListNode reverseList_2(ListNode head) {
        if (head == null || head.next == null)
            return head;
        ListNode newListNode = new ListNode();
        newListNode.val = "-1";

        while (head.next != null) {
            ListNode next = head.next;

            head.next = newListNode.next;//当前的节点拼接上已经转换好的节点，即将当前节点加到newListNode的根节点上（二节点）
            newListNode.next = head;

            head = next;
        }

        return newListNode.next;
    }







    static class ListNode {
        public String val;
        public ListNode next;
    }

    private static ListNode listNode;
    public static ListNode getListNode() {
        if (listNode == null) {
            listNode = new ListNode();
            ListNode a = listNode;
            ListNode startNode = null;

            for (int i = 1; i < 11; i++) {
                a.val = "" + i;
                a.next = new ListNode();
                if (i == 3)
                    startNode = a;
                if (i == 10) {
                    //a.next = startNode;
                }
                a = a.next;
            }
        }

        return listNode;
    }

}
